<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>算法设计与分析之贪心算法 | 路漫漫其修远兮，吾将上下而求索</title><meta name="keywords" content="上课笔记 - 算法"><meta name="author" content="Charles Yan"><meta name="copyright" content="Charles Yan"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="包括贪心算法的概念以及解题方法，最后附上课后习题以及答案">
<meta property="og:type" content="article">
<meta property="og:title" content="算法设计与分析之贪心算法">
<meta property="og:url" content="https://www.charlesyan.cn/2020/11/16/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%88%E7%AE%97%E6%B3%95%E7%90%86%E8%A7%A3%E5%8A%A0%E7%BB%8F%E5%85%B8%E4%BE%8B%E9%A2%98%E8%A7%A3%E6%9E%90%EF%BC%89/index.html">
<meta property="og:site_name" content="路漫漫其修远兮，吾将上下而求索">
<meta property="og:description" content="包括贪心算法的概念以及解题方法，最后附上课后习题以及答案">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/12998.jpg">
<meta property="article:published_time" content="2020-11-16T05:16:49.911Z">
<meta property="article:modified_time" content="2020-12-25T12:19:16.198Z">
<meta property="article:author" content="Charles Yan">
<meta property="article:tag" content="上课笔记 - 算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/12998.jpg"><link rel="shortcut icon" href="/img/favicon.ico"><link rel="canonical" href="https://www.charlesyan.cn/2020/11/16/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%88%E7%AE%97%E6%B3%95%E7%90%86%E8%A7%A3%E5%8A%A0%E7%BB%8F%E5%85%B8%E4%BE%8B%E9%A2%98%E8%A7%A3%E6%9E%90%EF%BC%89/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'mediumZoom',
  Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#121212","position":"bottom-left"},
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: true
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '算法设计与分析之贪心算法',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2020-12-25 20:19:16'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const fontSizeVal = saveToLocal.get('global-font-size')
    if (fontSizeVal !== undefined) {
      document.documentElement.style.setProperty('--global-font-size', fontSizeVal + 'px')
    }
    })(window)</script><link rel="stylesheet" href="/css/selfdesign.css" media="defer" onload="this.media='all'"><meta name="generator" content="Hexo 5.4.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="/img/My%20avatar.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">37</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">22</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">12</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fa fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fa fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fa fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/messageboard/"><i class="fa-fw fa fa-coffee"></i><span> 留言板</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fa fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fa fa-heart"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fa fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fa fa-film"></i><span> 电影</span></a></li><li><a class="site-page child" href="/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/12998.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">路漫漫其修远兮，吾将上下而求索</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fa fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fa fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fa fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/messageboard/"><i class="fa-fw fa fa-coffee"></i><span> 留言板</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fa fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fa fa-heart"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fa fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fa fa-film"></i><span> 电影</span></a></li><li><a class="site-page child" href="/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">算法设计与分析之贪心算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-11-16T05:16:49.911Z" title="发表于 2020-11-16 13:16:49">2020-11-16</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2020-12-25T12:19:16.198Z" title="更新于 2020-12-25 20:19:16">2020-12-25</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90%E4%B8%8E%E8%AE%BE%E8%AE%A1/">算法分析与设计</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">2.4k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>9分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="算法设计与分析之贪心算法"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h3 id="贪心算法（算法理解加经典例题解析）"><a href="#贪心算法（算法理解加经典例题解析）" class="headerlink" title="贪心算法（算法理解加经典例题解析）"></a>贪心算法（算法理解加经典例题解析）</h3><h3 id="一、概要"><a href="#一、概要" class="headerlink" title="一、概要"></a>一、概要</h3><h4 id="1-什么是贪心算法？"><a href="#1-什么是贪心算法？" class="headerlink" title="1. 什么是贪心算法？"></a>1. 什么是贪心算法？</h4><ul>
<li><p>顾名思义，总是在作出当前看来最好的选择。</p>
</li>
<li><p>并不从整体最优考虑，只是某种程度上的局部最优选择。</p>
</li>
<li><p>不一定是最优解，但往往是最接近最优解的。</p>
</li>
</ul>
<h4 id="2-贪心设计策略"><a href="#2-贪心设计策略" class="headerlink" title="2. 贪心设计策略"></a>2. 贪心设计策略</h4><ol>
<li>活动安排问题</li>
<li>最优装载问题</li>
<li>哈夫曼编码</li>
<li>单源最短路径</li>
<li>最小生成树</li>
<li>多机调度问题</li>
</ol>
<h4 id="3-贪心选择性质"><a href="#3-贪心选择性质" class="headerlink" title="3. 贪心选择性质"></a>3. 贪心选择性质</h4><ol>
<li><p>贪心算法通常自顶向下的方式进行</p>
</li>
<li><p>最优子结构性质</p>
</li>
</ol>
<h3 id="二、习题解析"><a href="#二、习题解析" class="headerlink" title="二、习题解析"></a>二、习题解析</h3><h4 id="1-会场安排问题"><a href="#1-会场安排问题" class="headerlink" title="1. 会场安排问题"></a>1. 会场安排问题</h4><p><strong>题目：</strong> 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每个活动作为一个图的顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相当于要找的最小会场数。）</p>
<p><strong>数据输入：</strong> 第一行有一个正整数$k$ ，表示有$k$ 个待安排的活动，接下来的$k$ 行中，每行有2个正整数，分别表示$k$ 个待安排的活动屁那个的开始时间和结束时间。时间以0点开始的分钟计。</p>
<p><strong>结果输出：</strong> 将计算的最少会场数输出</p>
<p><strong>输入：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">5</span></span><br><span class="line"><span class="number">1</span> <span class="number">23</span></span><br><span class="line"><span class="number">12</span> <span class="number">28</span></span><br><span class="line"><span class="number">25</span> <span class="number">35</span></span><br><span class="line"><span class="number">27</span> <span class="number">80</span></span><br><span class="line"><span class="number">36</span> <span class="number">50</span></span><br></pre></td></tr></table></figure>
<p><strong>输出：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">3</span></span><br></pre></td></tr></table></figure>
<p><strong>1.题解：</strong> 这里采用贪心策略，每一步最优，即下一个会议的开始时间大于等于之前任意一个会议的结束时间，那么这两个会议可以安排在同一个会议室。如果该会议开始了，但是之前的会议都还没有结束，那么就另起一个会议室。</p>
<p>需要注意的是，当两个会议安排在同一个会议室时，那么下次判断时间的时候要以后者的会议结束时间为准，要将前者的会议时间覆盖。</p>
<p>在这里，用到的会议室总数用$num$记录，$flag$记录的是第$i$个会议用在哪个会议室（更新）</p>
<p><strong>代码：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="comment">//会场安排问题，贪心策略，每一步最优</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">meeting</span> &#123;</span></span><br><span class="line">	<span class="keyword">int</span> start;</span><br><span class="line">	<span class="keyword">int</span> end;</span><br><span class="line">&#125;m[<span class="number">1000</span>];</span><br><span class="line"><span class="keyword">int</span> flag[<span class="number">1000</span>] = &#123;<span class="number">0</span>&#125;;<span class="comment">//记录会场个数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i&lt;n; i++) &#123;</span><br><span class="line">		cin&gt;&gt;m[i].start;</span><br><span class="line">		cin&gt;&gt;m[i].end;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> start = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> temp = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> num = <span class="number">1</span>;<span class="comment">//会场个数</span></span><br><span class="line">	flag[start] = num;<span class="comment">//在哪个会场开会</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i&lt;n; i++) &#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j = start;j&lt;i;j++)&#123;</span><br><span class="line">		<span class="keyword">if</span> (m[j].end&lt;=m[i].start &amp;&amp; flag[j]) &#123;</span><br><span class="line">			flag[i] = flag[j];</span><br><span class="line">			flag[j] = <span class="number">0</span>;</span><br><span class="line">			temp = <span class="number">1</span>;</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (temp == <span class="number">0</span>) &#123;</span><br><span class="line">			num++;</span><br><span class="line">			flag[i] = num;</span><br><span class="line">		&#125;<span class="keyword">else</span> temp = <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	cout&lt;&lt;num&lt;&lt;endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h4 id="2-最优合并问题"><a href="#2-最优合并问题" class="headerlink" title="2. 最优合并问题"></a>2. 最优合并问题</h4><p><strong>题目：</strong> 给定$k$个排好序的序列$s1,s2,…,sk$，用$2$路合并算法将这$k$个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为$m$和$n$的序列需要$m+n-1$次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需要的总比较次数最少。 </p>
<p><strong>数据输入：</strong> 第一行有一个正整数$k$，表示有$k$个待合并序列。接下来的一行中，有$k$个正整数，表示个待合并序列的长度。</p>
<p><strong>数据输出：</strong> 将计算的最多比较次数和最少比较次数输出</p>
<p><strong>输入：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">4</span></span><br><span class="line"><span class="number">5</span> <span class="number">12</span> <span class="number">11</span> <span class="number">2</span></span><br></pre></td></tr></table></figure>
<p><strong>输出：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">78</span> <span class="number">52</span></span><br></pre></td></tr></table></figure>
<p><strong>2.题解：</strong> 贪心策略，局部最优考虑。比较一次需要$m+n-1$次，那么对于最少比较次数 ，每一个都使m，n是最小的两个值，对于例子：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>当前序列</th>
<th>合并</th>
<th>总和</th>
<th>剩余序列</th>
</tr>
</thead>
<tbody>
<tr>
<td>2,5,11,12</td>
<td>2+5 = 7</td>
<td>2+5-1 = 6</td>
<td>7,11,12</td>
</tr>
<tr>
<td>7,11,12</td>
<td>7+11 = 18</td>
<td>6+18-1 = 23</td>
<td>12,18</td>
</tr>
<tr>
<td>12,18</td>
<td>12+18 = 30</td>
<td>23+30-1 = 52</td>
<td>30</td>
</tr>
</tbody>
</table>
</div>
<p>同理最大比较次数与之相反。</p>
<p><strong>代码：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">1. 最优升序比较</span></span><br><span class="line"><span class="comment">2. 最差降序比较</span></span><br><span class="line"><span class="comment">贪心策略，每一步最优</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">int</span> n;<span class="comment">//序列个数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">cmp</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a&gt;b;</span><br><span class="line">&#125;<span class="comment">//降序</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Huffman</span><span class="params">(<span class="keyword">int</span> *a,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; n<span class="number">-1</span>;i++) &#123;</span><br><span class="line">		a[i+<span class="number">1</span>] = a[i]+a[i+<span class="number">1</span>];</span><br><span class="line">		sum += a[i+<span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">1000</span>] = &#123;&#125;;<span class="comment">//升序</span></span><br><span class="line">	<span class="keyword">int</span> b[<span class="number">1000</span>] = &#123;&#125;;<span class="comment">//降序</span></span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>;i&lt;n;i++)&#123; </span><br><span class="line">		cin&gt;&gt;a[i];</span><br><span class="line">		b[i] = a[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//排序---最优</span></span><br><span class="line">	<span class="built_in">sort</span>(a, a+n);<span class="comment">//升序</span></span><br><span class="line">	<span class="built_in">sort</span>(b, b+n,cmp);</span><br><span class="line">	cout&lt;&lt;<span class="built_in">Huffman</span>(a, n)-n+<span class="number">1</span>&lt;&lt;endl;</span><br><span class="line">	cout&lt;&lt;<span class="built_in">Huffman</span>(b, n)-n+<span class="number">1</span>&lt;&lt;endl;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="3-最优服务次序问题"><a href="#3-最优服务次序问题" class="headerlink" title="3. 最优服务次序问题"></a>3. 最优服务次序问题</h4><p><strong>题目：</strong> 设有$n$个顾客同时等待一项服务，顾客$i$需要的服务时间为$t_i(1\leq i \leq n  )$。应该如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以$n$。</p>
<p><strong>数据输入：</strong> 第一行正整数$n$，表示有$n$个顾客。接下来的1行中，有$n$个正整数，表示n个顾客需要的服务时间。</p>
<p><strong>结果输出：</strong> 将计算的最小平均等待时间输出。</p>
<p><strong>输入：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">10</span></span><br><span class="line"><span class="number">56</span> <span class="number">12</span> <span class="number">1</span> <span class="number">99</span> <span class="number">1000</span> <span class="number">234</span> <span class="number">33</span> <span class="number">55</span> <span class="number">99</span> <span class="number">812</span></span><br></pre></td></tr></table></figure>
<p><strong>输出：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">532.00</span></span><br></pre></td></tr></table></figure>
<p><strong>3.题解：</strong> 贪心策略，最短服务时间优先，在人数一定时，总的等待时间越短，平均时间也就越短，因此，现将所有顾客等待时间进行升序排列，然后求和。</p>
<p><strong>代码：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="comment">//最优服务次序问题，贪心策略，即最短服务时间优先，类似于最优合并排序</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">1000</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">Huffman</span><span class="params">(<span class="keyword">int</span> *a,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>;i &lt; n;i++) a[i] += a[i<span class="number">-1</span>];</span><br><span class="line">	<span class="keyword">double</span> t = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i&lt;n;i++) t += a[i];</span><br><span class="line">	t /= n;</span><br><span class="line">	<span class="keyword">return</span> t;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span> </span>&#123;</span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; n;i++) cin &gt;&gt; a[i];</span><br><span class="line">	<span class="built_in">sort</span>(a,a+n);<span class="comment">//升序排列</span></span><br><span class="line">	cout&lt;&lt;<span class="built_in">Huffman</span>(a, n)&lt;&lt;endl;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="4-虚拟汽车加油站问题"><a href="#4-虚拟汽车加油站问题" class="headerlink" title="4. 虚拟汽车加油站问题"></a>4. 虚拟汽车加油站问题</h4><p><strong>问题描述：</strong> 一辆虚拟汽车加满油后可行驶$nkm$。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。</p>
<p><strong>数据输入：</strong> 第一行有2个正整数$n$和$k$，表示汽车加满油后可行驶$nkm$，且旅途中有$k$个加油站。接下来的1行中有$k+1$个整数，表示第$k$个加油站与第$k-1$个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第$k+1$个加油站表示目的地。</p>
<p><strong>数据输出：</strong> 将计算的最少加油次数输出。</p>
<p><strong>输入：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">7</span> <span class="number">7</span></span><br><span class="line"><span class="number">1</span> <span class="number">2</span> <span class="number">3</span> <span class="number">4</span> <span class="number">5</span> <span class="number">1</span> <span class="number">6</span> <span class="number">6</span></span><br></pre></td></tr></table></figure>
<p><strong>输出：</strong> </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">4</span></span><br></pre></td></tr></table></figure>
<p><strong>4.题解：</strong> 贪心策略，最远加油站优先，从前往后走，每一次都计算出最远能到达的加油站。由局部最优解最终算出全局最优解</p>
<p><strong>代码：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="comment">//贪心策略，最远加油站优先</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">greedy</span><span class="params">(<span class="keyword">int</span> *a,<span class="keyword">int</span> n,<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> sum = <span class="number">0</span>,s = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>;i&lt;=k;i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (a[i] &gt; n) &#123;</span><br><span class="line">			cout&lt;&lt;<span class="string">&quot;ERROR!&quot;</span>&lt;&lt;endl;</span><br><span class="line">			<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>;i&lt; k;i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (n&gt;= a[i]+a[i+<span class="number">1</span>]) &#123;</span><br><span class="line">			a[i+<span class="number">1</span>] += a[i];</span><br><span class="line">		&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">			sum++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n,k;</span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">1000</span>] = &#123;&#125;;</span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	cin&gt;&gt;k;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i&lt;=n;i++) cin&gt;&gt;a[i];</span><br><span class="line">	cout&lt;&lt;<span class="built_in">greedy</span>(a,n,k);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="5-最优分解问题"><a href="#5-最优分解问题" class="headerlink" title="5. 最优分解问题"></a>5. 最优分解问题</h4><p><strong>问题描述：</strong> 设n是一个正整数。现要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大。</p>
<p><strong>数据输入：</strong> 第一行正整数n</p>
<p><strong>结果输出：</strong> 将计算的最大乘积输出</p>
<p><strong>输入：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">10</span></span><br></pre></td></tr></table></figure>
<p><strong>输出：</strong> </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">30</span></span><br></pre></td></tr></table></figure>
<p><strong>5.题解：</strong> 将n分成从2开始的连续自然数的和，如果最后剩下一个数，将此数在后项优先的方式下均匀的地分给前面各项。对于10，可以分成2，3，4最后还剩1，以后项优先的方式分配，所以就是2，3，5。结果就是$(2\times3\times5 = 30)$  </p>
<p>原理：在固定总和数的情况下，两个数相差越小，乘积越大，因数越多，乘积越大。</p>
<p><strong>代码：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="comment">//最优分解问题</span></span><br><span class="line"><span class="comment">//贪心算法：将n分解为以2开始连续自然数之和</span></span><br><span class="line"><span class="comment">//原理：在固定总和数的情况下，两个数相差越小，乘积越大，因数越多，乘积越大。</span></span><br><span class="line"><span class="comment">//几何意义解释：固定周长，正方形面积大于长方形</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">maxArea</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(n &lt; <span class="number">2</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>(n == <span class="number">2</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">1000</span>] = &#123;&#125;;</span><br><span class="line">	a[<span class="number">0</span>] = <span class="number">2</span>;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line">	n -= a[<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">0</span>; ;i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(n &gt;= a[i]+<span class="number">1</span>)&#123;</span><br><span class="line">		a[i+<span class="number">1</span>] = a[i]+<span class="number">1</span>;</span><br><span class="line">		n = n - a[i+<span class="number">1</span>];</span><br><span class="line">	  &#125;<span class="keyword">else</span> <span class="keyword">break</span>;</span><br><span class="line">  &#125;</span><br><span class="line">	<span class="keyword">int</span> t = i;<span class="comment">//保存最后一位</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j = n;j&gt;<span class="number">0</span>;j--)&#123;</span><br><span class="line">		<span class="keyword">if</span>(t) a[t--] += <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			a[t] += <span class="number">1</span>;</span><br><span class="line">			t = i;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//求乘积</span></span><br><span class="line">	<span class="keyword">int</span> sum = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>;j&lt;=i;j++) sum = sum * a[j];</span><br><span class="line">	<span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">int</span> argc, <span class="keyword">char</span> *argv[])</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	cout&lt;&lt;<span class="built_in">maxArea</span>(n);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Charles Yan</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://www.charlesyan.cn/2020/11/16/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%88%E7%AE%97%E6%B3%95%E7%90%86%E8%A7%A3%E5%8A%A0%E7%BB%8F%E5%85%B8%E4%BE%8B%E9%A2%98%E8%A7%A3%E6%9E%90%EF%BC%89/">https://www.charlesyan.cn/2020/11/16/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%88%E7%AE%97%E6%B3%95%E7%90%86%E8%A7%A3%E5%8A%A0%E7%BB%8F%E5%85%B8%E4%BE%8B%E9%A2%98%E8%A7%A3%E6%9E%90%EF%BC%89/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://www.charlesyan.cn" target="_blank">路漫漫其修远兮，吾将上下而求索</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E4%B8%8A%E8%AF%BE%E7%AC%94%E8%AE%B0-%E7%AE%97%E6%B3%95/">上课笔记 - 算法</a></div><div class="post_share"><div class="social-share" data-image="https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/12998.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button button--animated"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/img/IMG_0003.jpeg" target="_blank"><img class="post-qr-code-img" src="/img/IMG_0003.jpeg" alt="wechat"/></a><div class="post-qr-code-desc">wechat</div></li><li class="reward-item"><a href="/img/IMG_0004.jpeg" target="_blank"><img class="post-qr-code-img" src="/img/IMG_0004.jpeg" alt="alipay"/></a><div class="post-qr-code-desc">alipay</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2020/11/30/%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90%E4%B8%8E%E8%AE%BE%E8%AE%A1%E4%B9%8B%E5%9B%9E%E6%BA%AF%E6%B3%95/"><img class="prev-cover" src="https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/7801.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info"></div></div></a></div><div class="next-post pull-right"><a href="/2020/11/14/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E4%B9%8B%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/"><img class="next-cover" src="https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/7801.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">算法设计与分析之动态规划</div></div></a></div></nav><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="twikoo-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%88%E7%AE%97%E6%B3%95%E7%90%86%E8%A7%A3%E5%8A%A0%E7%BB%8F%E5%85%B8%E4%BE%8B%E9%A2%98%E8%A7%A3%E6%9E%90%EF%BC%89"><span class="toc-number">1.</span> <span class="toc-text">贪心算法（算法理解加经典例题解析）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E6%A6%82%E8%A6%81"><span class="toc-number">2.</span> <span class="toc-text">一、概要</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-%E4%BB%80%E4%B9%88%E6%98%AF%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%EF%BC%9F"><span class="toc-number">2.1.</span> <span class="toc-text">1. 什么是贪心算法？</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-%E8%B4%AA%E5%BF%83%E8%AE%BE%E8%AE%A1%E7%AD%96%E7%95%A5"><span class="toc-number">2.2.</span> <span class="toc-text">2. 贪心设计策略</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3-%E8%B4%AA%E5%BF%83%E9%80%89%E6%8B%A9%E6%80%A7%E8%B4%A8"><span class="toc-number">2.3.</span> <span class="toc-text">3. 贪心选择性质</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E4%B9%A0%E9%A2%98%E8%A7%A3%E6%9E%90"><span class="toc-number">3.</span> <span class="toc-text">二、习题解析</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-%E4%BC%9A%E5%9C%BA%E5%AE%89%E6%8E%92%E9%97%AE%E9%A2%98"><span class="toc-number">3.1.</span> <span class="toc-text">1. 会场安排问题</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-%E6%9C%80%E4%BC%98%E5%90%88%E5%B9%B6%E9%97%AE%E9%A2%98"><span class="toc-number">3.2.</span> <span class="toc-text">2. 最优合并问题</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3-%E6%9C%80%E4%BC%98%E6%9C%8D%E5%8A%A1%E6%AC%A1%E5%BA%8F%E9%97%AE%E9%A2%98"><span class="toc-number">3.3.</span> <span class="toc-text">3. 最优服务次序问题</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-%E8%99%9A%E6%8B%9F%E6%B1%BD%E8%BD%A6%E5%8A%A0%E6%B2%B9%E7%AB%99%E9%97%AE%E9%A2%98"><span class="toc-number">3.4.</span> <span class="toc-text">4. 虚拟汽车加油站问题</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-%E6%9C%80%E4%BC%98%E5%88%86%E8%A7%A3%E9%97%AE%E9%A2%98"><span class="toc-number">3.5.</span> <span class="toc-text">5. 最优分解问题</span></a></li></ol></li></ol></div></div></div></div></main><footer id="footer" style="background-image: url('https://gitee.com/yan_zilong/picgo/raw/master/img/Blog/post/密码学复习提纲/12998.jpg')"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2021 By Charles Yan</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">Hi, welcome to my <a target="_blank" rel="noopener" href="https:charlesyan.cn/">blog</a>!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="font-plus" type="button" title="放大字体"><i class="fas fa-plus"></i></button><button id="font-minus" type="button" title="缩小字体"><i class="fas fa-minus"></i></button><button id="translateLink" type="button" title="简繁转换">简</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="chat_btn" type="button" title="rightside.chat_btn"><i class="fas fa-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">本地搜索</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div></div><hr/><div id="local-search-results"></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script>function panguFn () {
  if (typeof pangu === 'object') pangu.autoSpacingPage()
  else {
    getScript('https://cdn.jsdelivr.net/npm/pangu/dist/browser/pangu.min.js')
      .then(() => {
        pangu.autoSpacingPage()
      })
  }
}

function panguInit () {
  if (false){
    GLOBAL_CONFIG_SITE.isPost && panguFn()
  } else {
    panguFn()
  }
}

document.addEventListener('DOMContentLoaded', panguInit)</script><script src="/js/search/local-search.js"></script><script>var preloader = {
  endLoading: () => {
    document.body.style.overflow = 'auto';
    document.getElementById('loading-box').classList.add("loaded")
  },
  initLoading: () => {
    document.body.style.overflow = '';
    document.getElementById('loading-box').classList.remove("loaded")

  }
}
window.addEventListener('load',preloader.endLoading())</script><div class="js-pjax"><script>if (document.getElementsByClassName('mermaid').length) {
  if (window.mermaidJsLoad) mermaid.init()
  else {
    getScript('https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js').then(() => {
      window.mermaidJsLoad = true
      mermaid.initialize({
        theme: 'default',
      })
      false && mermaid.init()
    })
  }
}</script><script>(()=>{
  const $countDom = document.getElementById('twikoo-count')
  const init = () => {
    twikoo.init(Object.assign({
      el: '#twikoo-wrap',
      envId: 'https://twikoo-beta-tawny.vercel.app/',
      region: ''
    }, null))
  }

  const getCount = () => {
    twikoo.getCommentsCount({
      envId: 'https://twikoo-beta-tawny.vercel.app/',
      region: '',
      urls: [window.location.pathname],
      includeReply: false
    }).then(function (res) {
      $countDom.innerText = res[0].count
    }).catch(function (err) {
      console.error(err);
    });
  }

  const loadTwikoo = (bool = false) => {
    if (typeof twikoo === 'object') {
      init()
      bool && $countDom && setTimeout(getCount,0)
    } else {
      getScript('https://cdn.jsdelivr.net/npm/twikoo/dist/twikoo.all.min.js').then(()=> {
        init()
        bool && $countDom && setTimeout(getCount,0)
      })
    }
  }

  if ('Twikoo' === 'Twikoo' || !false) {
    if (false) btf.loadComment(document.getElementById('twikoo-wrap'), loadTwikoo)
    else loadTwikoo(true)
  } else {
    window.loadOtherComment = () => {
      loadTwikoo()
    }
  }
})()</script></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>